//
//  ProblemMS1711.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 17.11. 单词距离
 有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

 示例：

 输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
 输出：1
 */
@objcMembers class ProblemMS1711: NSObject {
    func solution() {
        print(findClosestDouble(["I","am","a","student","from","a","university","in","a","city"], "a", "student"))
    }
    
    /*
     暴力破解：
     1: 找到所有的word1的位置，找到所有word2的位置
     2: 算一下哪个位置最小
     */
    func findClosest(_ words: [String], _ word1: String, _ word2: String) -> Int {
        if word1 == word2 {
            return 0
        }
        var list1:[Int] = []
        var list2:[Int] = []
        for (i,word) in words.enumerated() {
            if word == word1 {
                list1.append(i)
            } else if word == word2 {
                list2.append(i)
            }
        }
        
        // 暴力求最小值
        var minVlaue = words.count
        for i in list1 {
            for j in list2 {
                if j > i {
                    minVlaue = min(minVlaue, j - i)
                } else {
                    minVlaue = min(minVlaue, i - j)
                }
            }
        }

        return minVlaue
    }
    
    /*
     双指针：
     1: 定义一个不动的指针 left，一个动态的指针right
     2: 遍历数组，寻找word1和word2，找到第一个，就让left指向他
     3: 假如left = word1，那么从继续遍历寻找word1和word2，
        3.1 找到word2 就计算最小值
        3.2 找到word1 就更新left到这个位置
     */
    func findClosestDouble(_ words: [String], _ word1: String, _ word2: String) -> Int {
        if word1 == word2 {
            return 0
        }
        
        var left:Int = -words.count
        var minValue = words.count
        var curWord: String? = nil
        
        for (i, word) in words.enumerated() {
            if word == word1 || word == word2 {
                if curWord == word {
                    left = i
                } else {
                    minValue = min(minValue, i - left)
                    left = i
                    curWord = word
                }
            }
        }

        return minValue == words.count ? -1 : minValue
    }
}
